package sliding_window

/*
992.给定一个正整数数组 nums和一个整数 k，返回 num中 「好子数组」的数目。
如果 nums 的某个子数组中不同整数的个数【恰好】为 k，则称 nums 的这个连续、不一定不同的子数组为 「好子数组 」。

例如，[1,2,3,1,2] 中有3个不同的整数：1，2，以及3。
子数组 是数组的 连续 部分。

示例 1：
输入：nums = [1,2,1,2,3], k = 2
输出：7
解释：恰好由 2 个不同整数组成的子数组：[1,2], [2,1], [1,2], [2,3], [1,2,1], [2,1,2], [1,2,1,2].

示例 2：
输入：nums = [1,2,1,3,4], k = 3
输出：3
解释：恰好由 3 个不同整数组成的子数组：[1,2,1,3], [2,1,3], [1,3,4].
*/
//滑动窗口：原问题就转换成为求解「最多存在 K 个不同整数的子区间的个数」与 「最多存在 K−1 个不同整数的子区间的个数」，它们其实是一个问题。

//时间复杂度：O(N)，这里 N 是输入数组的长度；
//空间复杂度：O(N)，使用了常数个变量、频数数组的长度为N+1。
func atMostKDistinct(nums []int, k int) (cnt int) {
	left, right, freq, valid := 0, 0, make([]int, len(nums)+1), 0
	for right < len(nums) {
		c := nums[right]
		if freq[c] == 0 {
			valid++
		}
		freq[c]++
		right++

		//最多存在K个不同整数的子区间的个数
		for valid > k {
			d := nums[left]
			freq[d]--
			if freq[d] == 0 {
				valid--
			}
			//左移窗口，收缩窗口，得到可行解
			left++
		}

		//所有的 左边界固定前提下，根据右边界最右的下标，计算出来的子区间的个数就是整个函数要返回的值。
		cnt += right - left

	}

	return
}
func subArraysWithKDistinct(nums []int, k int) (cnt int) {
	return atMostKDistinct(nums, k) - atMostKDistinct(nums, k-1)
}

//滑动窗口+双指针
//当右端点向右移动时，左端点区间也同样向右移动。
//因为当我们在原有区间的右侧添加元素时，区间中的不同整数数量不会减少而只会不变或增加，因此我们需要在区间左侧删除一定元素，以保证区间内整数数量仍然为 k。
//
//于是我们可以用滑动窗口解决本题。
//和普通的滑动窗口解法的不同之处在于，我们需要记录两个左指针left1与left2 来表示左端点区间[left1,left2)。
//第一个左指针表示极大的包含k 个不同整数的区间的左端点，
//第二个左指针则表示极大的包含 k−1 个不同整数的区间的左端点。
//
//时间复杂度：O(n)，其中 n 是数组长度。我们至多只需要遍历该数组三次（右指针和两个左指针各一次）。
//空间复杂度：O(n)，其中 n 是数组长度。我们需要记录每一个数的出现次数，本题中数的大小不超过数组长度。
func subArraysWithKDistinctP(nums []int, k int) (cnt int) {
	num1, num2 := make([]int, len(nums)+1), make([]int, len(nums)+1)
	tot1, tot2, left1, left2 := 0, 0, 0, 0

	//expand window
	for _, v := range nums {
		if num1[v] == 0 {
			tot1++ // add the type num
		}
		num1[v]++

		if num2[v] == 0 {
			tot2++
		}
		num2[v]++

		//shrink the window k
		for tot1 > k {
			num1[nums[left1]]--
			if num1[nums[left1]] == 0 {
				tot1--
			}
			left1++
		}

		//shrink the window k1-1
		for tot2 > k-1 {
			num2[nums[left2]]--
			if num2[nums[left2]] == 0 {
				tot2--
			}
			left2++
		}

		cnt += left2 - left1
	}
	return

}
